import com.sun.source.util.Trees;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: ws
 * Date: 2024-01-23
 * Time: 15:37
 *
 * https://www.nowcoder.com/share/jump/7745334641706076548735
 */
import java.util.*;


public class BM101 {


    /**
     * Node 存储相关的信息同时重写比较方法
     *
     */
    static class Node implements Comparable<Node> {
        int cnt;// 频率
        int time;// 最新出生时间
        int key;
        int value;

        public Node(int cnt, int time, int key, int value) {
            this.cnt = cnt;
            this.time = time;
            this.key = key;
            this.value = value;
        }


        // 面试题：为什么重写比较方法，一定要重写 hashCode ？

        // 模仿 String 重写
        @Override
        public boolean equals(Object o) {
            if (this == o) {// 地址相同
                return true;
            }
            if (o instanceof Node) {// 内部属性相同
                Node node = (Node) o;
                return this.cnt == node.cnt && this.time == node.time;
            }
            return false;
        }

        @Override
        public int compareTo(Node o) {
            // 按照 LFU 的规则升序排列
            return cnt == o.cnt ? time - o.time : cnt - o.cnt;
        }

        @Override
        public int hashCode() {
            // 随机重写（方法不唯一）
            return cnt * 1000000007 + time;
        }
    }

    int CAPACITY;// 容量
    int TIME;// 当前的时间
    Map<Integer, Node> map;// 保证唯一
    SortedSet<Node>
            set;// 保证顺序（如果实力足够可以收搓双向链表）

    // 初始化
    public BM101() {
        TIME = 0;// 开始时间为 0
        map = new HashMap<>();
        set = new TreeSet<>();// AVL 树，保证顺序
    }

    public int get(int key) {
        if (CAPACITY == 0) {// 没有容量
            return -1;
        }
        // 元素不存在
        if (!map.containsKey(key)) {
            return -1;
        }
        // 拿出旧的缓存
        Node node = map.get(key);
        // 删除旧的
        set.remove(node);
        // 更新频率和最新存活时间
        node.cnt++;
        node.time = ++TIME;
        //重新添加回去
        set.add(node);
        map.put(key, node);
        // 返回结果
        return node.value;
    }

    public void set(int key, int value) {
        if (CAPACITY == 0) {
            return;
        }
        // 元素不存在
        if (!map.containsKey(key)) {
            // 容量已满
            if (map.size() == CAPACITY) {
                // 按照 LFU 的规则删除一个节点(即 set 的头结点)
                map.remove(set.first().key);
                set.remove(set.first());
            }
            // 新的缓存节点
            Node node = new Node(1, ++TIME, key, value);
            // 添加到 map 和 set
            map.put(key, node);
            set.add(node);
        } else {// 元素存在
            // 参考 get 的实现
            Node node = map.get(key);
            set.remove(node);
            node.cnt++;
            node.time = ++TIME;
            node.value = value;
            map.put(key, node);
            set.add(node);
        }
    }


    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * lfu design
     * @param operators int整型二维数组 ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    public int[] LFU (int[][] operators, int k) {
        CAPACITY = k;
        // 获得 get 的次数，predicate 断定式接口
        int len = (int) Arrays.stream(operators).filter(x -> x[0] == 2).count();
        int[] res = new int[len];
        int j = 0;
        // 遍历所有操作数组
        for (int[] operator : operators) {
            // set 操作
            if (operator[0] == 1) {
                set(operator[1], operator[2]);
            } else {// get 操作
                res[j++] = get(operator[1]);
            }
        }
        return res;
    }
}